#include <CGAL/Simple_cartesian.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <list>

typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_2                                   Point_2;
typedef CGAL::Polygon_2<Kernel>                           Polygon_2;
typedef CGAL::Polygon_with_holes_2<Kernel>                Polygon_with_holes_2;
typedef std::list<Polygon_with_holes_2>                   Pwh_list_2;

template<class Kernel, class Container>
void print_polygon(const CGAL::Polygon_2<Kernel, Container>& P)
{
	typename CGAL::Polygon_2<Kernel, Container>::Vertex_const_iterator vit;
	std::cout << "[ " << P.size() << " vertices:";
	for (vit = P.vertices_begin(); vit != P.vertices_end(); ++vit)
		std::cout << " (" << *vit << ')';
	std::cout << " ]" << std::endl;
}
template<class Kernel, class Container>
void print_polygon_with_holes(const CGAL::Polygon_with_holes_2<Kernel, Container> & pwh)
{
	if (!pwh.is_unbounded()) {
		std::cout << "{ Outer boundary = ";
		print_polygon(pwh.outer_boundary());
	}
	else
		std::cout << "{ Unbounded polygon." << std::endl;
	typename CGAL::Polygon_with_holes_2<Kernel, Container>::Hole_const_iterator hit;
	unsigned int k = 1;
	std::cout << " " << pwh.number_of_holes() << " holes:" << std::endl;
	for (hit = pwh.holes_begin(); hit != pwh.holes_end(); ++hit, ++k) {
		std::cout << " Hole #" << k << " = ";
		print_polygon(*hit);
	}
	std::cout << " }" << std::endl;
}

int main()
{
	// Construct the two input polygons.
	Polygon_2 P;
	P.push_back(Point_2(0, 0));
	P.push_back(Point_2(2, 0.3333333330));
	P.push_back(Point_2(1.8, 1.5));
	P.push_back(Point_2(1, 2));
	P.push_back(Point_2(0, 1.53333333300));
	std::cout << "P = "; print_polygon(P);
	Polygon_2 Q;
	Q.push_back(Point_2(2, 0.33333333300));
	Q.push_back(Point_2(4, 0.5));
	Q.push_back(Point_2(4, 1.5));
	Q.push_back(Point_2(3.5, 0.5));
	Q.push_back(Point_2(2, 1.53333333300));
	std::cout << "Q = "; print_polygon(Q);
	// Compute the union of P and Q.
	Polygon_with_holes_2 unionR;
	if (CGAL::join(P, Q, unionR)) {
		std::cout << "The union: ";
		print_polygon_with_holes(unionR);
	}
	else
		std::cout << "P and Q are disjoint and their union is trivial." << std::endl;
	std::cout << std::endl;
	// Compute the intersection of P and Q.
	Pwh_list_2                  intR;
	Pwh_list_2::const_iterator  it;
	CGAL::intersection(P, Q, std::back_inserter(intR));
	std::cout << "The intersection:" << std::endl;
	for (it = intR.begin(); it != intR.end(); ++it) {
		std::cout << "--> ";
		print_polygon_with_holes(*it);
	}
	return 0;
}

int main_3_2()
{
	// Construct the two input polygons.
	Polygon_2 P;
	P.push_back(Point_2(0, 0));
	P.push_back(Point_2(5, 0));
	P.push_back(Point_2(3.5, 1.5));
	P.push_back(Point_2(2.5, 0.5));
	P.push_back(Point_2(1.5, 1.5));
	std::cout << "P = "; print_polygon(P);
	Polygon_2 Q;
	Q.push_back(Point_2(0, 2));
	Q.push_back(Point_2(1.5, 0.5));
	Q.push_back(Point_2(2.5, 1.5));
	Q.push_back(Point_2(3.5, 0.5));
	Q.push_back(Point_2(5, 2));
	std::cout << "Q = "; print_polygon(Q);
	// Compute the union of P and Q.
	Polygon_with_holes_2 unionR;
	if (CGAL::join(P, Q, unionR)) {
		std::cout << "The union: ";
		print_polygon_with_holes(unionR);
	}
	else
		std::cout << "P and Q are disjoint and their union is trivial." << std::endl;
	std::cout << std::endl;
	// Compute the intersection of P and Q.
	Pwh_list_2                  intR;
	Pwh_list_2::const_iterator  it;
	CGAL::intersection(P, Q, std::back_inserter(intR));
	std::cout << "The intersection:" << std::endl;
	for (it = intR.begin(); it != intR.end(); ++it) {
		std::cout << "--> ";
		print_polygon_with_holes(*it);
	}
	return 0;
}


int main_3_1()
{
	Polygon_2 P;
	P.push_back(Point_2(-1, 1));
	P.push_back(Point_2(0, -1));
	P.push_back(Point_2(1, 1));
	std::cout << "P = "; print_polygon(P);
	Polygon_2 Q;
	Q.push_back(Point_2(-1, -1));
	Q.push_back(Point_2(1, -1));
	Q.push_back(Point_2(0, 1));
	std::cout << "Q = "; print_polygon(Q);
	if ((CGAL::do_intersect(P, Q)))
		std::cout << "The two polygons intersect in their interior." << std::endl;
	else
		std::cout << "The two polygons do not intersect." << std::endl;
	return 0;
}